#include <array>
#include <cstddef>
#include <string>
using namespace std;
class Trie {
private:
  struct node {
    char value = 0;
    bool isWord = false;
    array<struct node *, 26> child = {nullptr};
  };
  // 根节点
  struct node *_root;

public:
  Trie() { _root = new node; }

  void insert(string word) {
    // 插入字符串
    node *_node = _root;
    for (int i = 0; i < word.size(); i++) {
      if (_node->child[word[i] - 'a'] == nullptr) {
        _node->child[word[i] - 'a'] = new node;
        _node->child[word[i] - 'a']->value = word[i];
      }
      _node = _node->child[word[i] - 'a'];
    }
    _node->isWord = true;
  }

  bool search(string word) {
    node *_node = _root;
    for (int i = 0; i < word.size(); i++) {
      node *child = _node->child[word[i] - 'a'];
      if (child != nullptr) {
        _node = child;
      } else {
        return false;
      }
    }
    if (!_node->isWord) {
      return false;
    }
    return true;
  }

  bool startsWith(string prefix) {
    node *_node = _root;
    for (int i = 0; i < prefix.size(); i++) {
      node *child = _node->child[prefix[i] - 'a'];
      if (child != nullptr) {
        _node = child;
      } else {
        return false;
      }
    }
    return true;
  }
};